package com.nan.leetcode;
 class ListNode {
      int val;
      ListNode next;
      public ListNode(){

      }
     public ListNode(int val) {
         this.val = val;
         this.next=null;
     }

     public ListNode(int val, ListNode next) {
         this.val = val;
         this.next = next;
     }
 }
public class Main {
    //给你一个链表的头节点 head 和一个整数 val ，
    // 请你删除链表中所有满足 Node.val == val 的节点，并返回 新的头节点
    //先删除后面的节点，再处理头结点
    public ListNode removeElements(ListNode head, int val) {
        if(head==null){
            return null;
        }
        //删除操作要知道待删除节点的前一个节点的
        ListNode prev=head;//待删除节点前一个节点
        ListNode cur=head.next;//待删除节点
        while(cur!=null){
            if(cur.val==val){
                //找到要删除的节点了
                prev.next=cur.next;
                cur=prev.next;
            }else{
                prev=prev.next;
                cur=cur.next;
            }
        }
        //删除操作要单独考虑待删除元素是头结点的情况
        if(head.val==val){
            head=head.next;
        }
        return head;
    }


    //给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。
    public ListNode reverseList(ListNode head) {
        if(head==null){
            return null;
        }
        if(head.next==null){
            //链表中只有一个节点
            return head;
        }
        //处理一般情况
        ListNode newHead=null;
        ListNode prevNode=null;
        ListNode curNode=head;
        while(curNode!=null){
            //进入循环的时候，需要先设定好nextNode的位置
          ListNode  nextNode = curNode.next;
          if(nextNode==null){
              //说明此时curNode已经指向链表最后一个节点
              //也就是反转后的新链表的头节点
              newHead=curNode;
          }
          curNode.next=prevNode;//核心操作
          //更新引用的位置
            prevNode=curNode;
            curNode=nextNode;
        }
        return newHead;
    }
    public ListNode reverseList2(ListNode head) {
        if (head == null) {
            return null;
        }
        if (head.next == null) {
            return head;
        }
        ListNode prevNode = null;
        ListNode curNode = head;
        ListNode nextNode = curNode.next;
        ListNode newHead = null;
        while (curNode != null) {
            nextNode = curNode.next;
            if (curNode.next == null) {
                newHead = curNode;
            }
            curNode.next = prevNode;
            prevNode = curNode;
            curNode = nextNode;
        }
        return newHead;
    }


    //给定一个头结点为 head 的非空单链表，返回链表的中间结点。
    //如果有两个中间结点，则返回第二个中间结点。
    public int getLength(ListNode head){
        int length=0;
        for(ListNode cur=head;cur!=null;cur=cur.next){
            length++;
        }
        return length;
    }
    public ListNode middleNode(ListNode head) {
     if(head==null){
         return null;
     }
     //求链表的长度
        int length=getLength(head);
     //针对长度除以2，得到引用走的步数
        int steps=length/2;
        //控制引用往后走
        ListNode cur=head;
        for(int i=0;i<steps;i++){
            cur=cur.next;
        }
        return cur;
    }


    //输入一个链表，输出该链表中倒数第k个结点。
    public ListNode FindKthToTail(ListNode head,int k) {
        if(head==null){
            return null;
        }
        if(k<=0){
            return null;
        }
        int length=getLength(head);
        if(k>length){
            return null;
        }
        //得到倒数第k个节点，就让引用从头开始，走length-k步
        ListNode cur=head;
        int steps=length-k;
        for(int i=0;i<steps;i++){
                cur = cur.next;
        }
        return cur;
    }


    //将两个升序链表合并为一个新的 升序 链表并返回。
    // 新链表是通过拼接给定的两个链表的所有节点组成的。
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        if(list1==null){
            return list2;
        }
        if(list2==null){
            return list1;
        }
        //两个链表都非空，进行合并
        ListNode cur1=list1;
        ListNode cur2=list2;
        //创建一个新的链表，用来保存合并的结果
        //为了简化后续的插入操作，可以使用一个傀儡节点
        ListNode newHead=new ListNode(0);
        //后续需要频繁进行尾插，为了尾插方便，使用一个变量把链表的尾部记录下来，
        ListNode newTail=newHead;//链表一般都是用头结点来表示的，但
        // 是也可以通过其他引用记录其他位置，典型的就是记录尾结点
        //进行循环遍历两个链表，并比较，任意引用到达链表尾部，都算循环结束
        while(cur1!=null&&cur2!=null){
            if(cur1.val< cur2.val){
                //就把cur1插入到新的链表中，要判断新的链表是否为空
                // (有傀儡节点就不需要这步了）
                newTail.next=cur1;
                newTail=newTail.next;
                cur1=cur1.next;
            }else{
                //就把cur2插入到新链表中
                newTail.next=cur2;
                newTail=newTail.next;
                cur2=cur2.next;
            }
        }
        //当上述循环结束，一定有一个引用已经到达了链表尾部
        //于是就把另一个链表的剩余部分插入即可
        if(cur1==null){
            newTail.next=cur2;
        }else {
            newTail.next = cur1;
        }
        return newHead.next;
    }


    //现有一链表的头指针 ListNode* pHead，给一定值x，编写一段代码将所有
    // 小于x的结点排在其余结点之前，且不能改变原来的数据顺序，
    // 返回重新排列后的链表的头指针。
    public ListNode partition(ListNode pHead, int x) {
        if(pHead==null){
            return null;
        }
        if(pHead.next==null){
            return pHead;
        }
        //处理一般情况
        //为了方便后续的尾插工作，选择带傀儡节点的链表更方便
        ListNode smallHead=new ListNode(0);
        ListNode smallTail=smallHead;
        ListNode largeHead=new ListNode(0);
        ListNode largeTail=largeHead;
        for(ListNode cur=pHead;cur!=null;cur=cur.next){
            if(cur.val<x){
                //smallTail.next=cur;
                smallTail.next=new ListNode(cur.val);
                smallTail=smallTail.next;
            }else{
                largeTail.next=new ListNode(cur.val);
                largeTail=largeTail.next;
            }
        }
        //合并两个链表,直接收尾相接即可
        smallTail.next=largeHead.next;//注意都是傀儡节点
        return smallHead.next;
    }


    //在一个排序的链表中，存在重复的结点，请删除该链表中重复的结点，重复的结点不保留，
    // 返回链表头指针。
    // 例如，链表 1->2->3->3->4->4->5  处理后为 1->2->5
    public ListNode deleteDuplication(ListNode pHead) {
        if(pHead==null){
            return null;
        }
        if(pHead.next==null){
            //链表里面只有一个节点，
            return pHead;
        }
        //遍历链表，判定其中是否存在重复的节点
        ListNode newHead=new ListNode(0);//带傀儡节点的链表，用来存放结果
        ListNode newTail=newHead;
        ListNode cur=pHead;
        while(cur!=null){
            if(cur.next!=null&&cur.val==cur.next.val){
                //发现cur是重复节点,需要找到接下来不重复的节点位置
                while (cur!=null&&cur.next!=null&&cur.val==cur.next.val){
                    cur=cur.next;
                }
                cur=cur.next;
            }else{
                //发现cur不是重复节点，直接插入到newHead末尾即可
                newTail.next=new ListNode(cur.val);
                newTail=newTail.next;
                cur=cur.next;
            }
        }
        return newHead.next;
    }


    //对于一个链表，请设计一个时间复杂度为O(n),额外空间复杂度为O(1)的算法，
    // 判断其是否为回文结构。1,2,2,1
    public boolean chkPalindrome(ListNode A) {
        if(A==null){
            return true;
        }
        if(A.next==null){
            return true;
        }
        //1.把原来的链表复制一份；
        ListNode newHead=new ListNode(0);
        ListNode newTail=newHead;
        for(ListNode cur=A;cur!=null;cur=cur.next){
            newTail.next=new ListNode(cur.val);
            newTail=newTail.next;
        }
        ListNode B=newHead.next;
        // 再把新的链表逆置；
        ListNode prevNode=null;
        ListNode curNode=B;
        ListNode nextNode=curNode.next;
        while(curNode!=null){
            nextNode=curNode.next;
            if(curNode.next==null) {
                B=curNode;
            }
                curNode.next = prevNode;
                prevNode = curNode;
                curNode = nextNode;
        }
        // 对比两个链表是否一样
        ListNode cur1=A;
        ListNode cur2=B;
        while(cur1!=null&&cur2!=null){
            if(cur1.val!=cur2.val){
                return false;
            }
            cur1=cur1.next;
            cur2=cur2.next;
        }
        return true;
    }
    //空间复杂度为O（1）的版本
    //找到链表的中间的节点，把后半部分逆置，看前后是否一样
    public boolean chkPalindrome2(ListNode A){
        if(A==null){
            return true;
        }
        if(A.next==null){
            return true;
        }
        //找到中间节点
        int length=getLength(A);
        int steps=length/2;
        ListNode B=A;
        for(int i=0;i<steps;i++){
            B=B.next;
        }
        //经历了上面的循环，B指向了链表的中间
        //针对B这半个链表，进行逆置
        ListNode prev=null;
        ListNode cur=B;
        ListNode nextNode=cur.next;
        while(cur!=null){
            nextNode=cur.next;
            if(cur.next==null){
                B=cur;
            }
            prev=cur;
            cur=nextNode;
        }
        //对比两个半个链表是否一样
        ListNode cur1=A;
        ListNode cur2=B;
        while(cur1!=null&&cur2!=null){
            if(cur1.val!=cur2.val){
                return false;
            }
            cur1=cur1.next;
            cur2=cur2.next;
        }
        return true;
    }


    //给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。
    // 如果两个链表不存在相交节点，返回 null 。
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        //先求两个链表的长度
        int length1=getLength(headA);
        int length2=getLength(headB);
        //让长的链表先走
        if(length1>length2){
            int steps=length1-length2;
            for(int i=0;i<steps;i++){
                headA=headA.next;
            }
        }else{
            int steps=length2-length1;
            for(int i=0;i<steps;i++){
                headB=headB.next;
            }
        }
        //此时headA和headB已经在同一位置了，于是就同步往后走,看能否相遇
        while(headA!=null&&headB!=null){
            //此处比较的不是节点里面的val，而是节点对象的身份，比较的是地址。
            if(headA==headB){
                //相交了，交点也找到了
                return headA;
            }
            headA=headA.next;
            headB=headB.next;
        }
        return null;
    }


    //给你一个链表的头节点 head ，判断链表中是否有环。
    public boolean hasCycle(ListNode head) {
        //快慢指针，
        ListNode fast=head;
        ListNode slow=head;
        while(fast!=null&&fast.next!=null){
            fast=fast.next.next;//fast走两步
            slow=slow.next;//slow走一步
            if(fast==slow){
                return true;//带环
            }
        }
        return false;
    }


    //给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
    public ListNode detectCycle(ListNode head) {
        //快慢指针，先找到快慢指针重合的位置
        ListNode fast=head;
        ListNode slow=head;
        while(fast!=null&&fast.next!=null){
            fast=fast.next.next;//fast走两步
            slow=slow.next;//slow走一步
            if(fast==slow){//快慢指针重合了
                break;
            }
        }
        if(fast==null||fast.next==null){
            return null;//说明链表不带环
        }
        //如果带环就从链表头和fast、slow交汇位置同时出发，两个引用相遇位置就是环的入口
        ListNode cur1=head;
        ListNode cur2=fast;
        while(cur1!=cur2){
            cur1=cur1.next;
            cur2=cur2.next;
        }
        return cur1;
    }

    public static void print(ListNode head) {
        for (ListNode cur = head; cur != null; cur = cur.next) {
            System.out.println(cur.val);
        }
    }
    public static void main(String[] args) {
        ListNode head=new ListNode(1);
        Main main=new Main();
       print( main.removeElements(head,1));
    }
}
